
%----------------------
%      椭圆曲线
%----------------------

%\chapter{椭圆曲线}

%\begin{definition}{双周期函数}{fubi}
%	如果函数$f(z)$(z为复平面上的一个点)，有两个基本周期$2\omega,2 \omega '$,也就是说$f(z+2\omega)=f(z),f(z+2\omega')=f(z)$，则称$f(z)$为双周期函数。
%\end{definition}
%
%为了给出椭圆曲线的一般定义，我们再看看纯函数和定义。
%
%\begin{definition}{全纯函数}{fubi}
%	设D是复平面上的区域，如果函数$f(z)$在D的每个点处都可导，则称f(x)在D内是全纯的，也称解析的或正则的。在整个复平面上全纯的函数，称为整函数。
%\end{definition}
%
%\begin{definition}{亚纯函数}{fubi}
%	设D是复平面上的区域，如果函数$f(z)$在D内除可能具有极点外是全纯的，则称f(x)在D内是亚纯的，在有限复平面上亚纯的函数，简称为亚纯函数。
%\end{definition}
%
%\begin{definition}{椭圆函数}{fubi}
%	双周期的亚纯函数称为椭圆函数。
%\end{definition}
%常见的Weierstrass()椭圆函数和雅可比椭圆函数。
椭圆曲线是黎曼几何的一个研究内容，也是代数几何中重要的一类研究对象，一个椭圆曲线是一个连通黎曼曲面，关于椭圆曲线的详细介绍，可以参考Joseph H. Silverman的“The Arithmetic of Elliptic Curves”(椭圆曲线算数)一书。下面我们引用一段椭圆曲线的英文介绍。\par
\vspace{0.5cm}
\textit{Classically in complex geometry, an elliptic curve is a connected Riemann surface (a connected compact 1-dimensional complex manifold) of genus 1, hence it is a torus equipped with the structure of a complex manifold, or equivalently with conformal structure.}
\par
\textit{The curious term “elliptic” is a remnant from the 19th century, a back-formation which refers to elliptic functions (generalizing circular functions, i.e., the classical trigonometric functions) and their natural domains as Riemann surfaces.}
\par
\textit{In more modern frameworks and in the generality of algebraic geometry, an elliptic curve over a field k or indeed over any commutative ring may be defined as a complete irreducible non-singular algebraic curve of arithmetic genus-1 over k, or even as a certain type of algebraic group scheme.}
\par
\textit{Elliptic curves have many remarkable properties, and their deeper arithmetic study is one of the most profound subjects in present-day mathematics.}\footnote{来源于\url{https://ncatlab.org/nlab/show/elliptic+curve}}
\par
\vspace{0.5cm}

\section{基本概念}
椭圆曲线(elliptic curve) 是指由Weierstrass韦尔斯特拉(中文翻译有韦尔斯特拉、魏尔斯特拉斯)方程确定的平面，韦尔斯特拉方程为：$E:y^2+axy+by = x^3+cx^2+dx+e$,E是Elliptic curve的缩写，表示这个方程描述了一个椭圆曲线,其中a，b，c，d和e属于域F，F可以是有理数域、复数域、有限域，密码学中通常采用有限域。\par
下面我们用Sagemath绘制几个实数域上的椭圆曲线。\par

\begin{example}
	椭圆曲线：$y^2=x^3-2x$\par
	\begin{SageMath}{椭圆曲线} 
		\begin{verbatim}
		# y^2=x^3-2x
		p= plot(EllipticCurve([0,0,0,-2,0]),gridlines='true', xmin=-4, xmax=4, 
		   ymin=-3, ymax=3,legend_label='$y^2=x^3-2x$')
		show(p)
		\end{verbatim}
	\end{SageMath}
	\begin{figure}[!htbp]
		\centering
		\includegraphics[width=0.6\textwidth]{figure/EC-1.png}
		\caption{椭圆曲线$y^2=x^3-2x$\label{fig:EC-1}}
	\end{figure}
\end{example}

\begin{example}
	椭圆曲线：$y^2=x^3-2x+1$\par
	\begin{SageMath}{椭圆曲线} 
		\begin{verbatim}
		# y^2=x^3-2x
		p= plot(EllipticCurve([0,0,0,-2,1]),gridlines='true', xmin=-4, xmax=4, 
		   ymin=-3, ymax=3,legend_label='$y^2=x^3-2x+1$')
		show(p)
		\end{verbatim}
	\end{SageMath}
	\begin{figure}[!htbp]
		\centering
		\includegraphics[width=0.6\textwidth]{figure/EC-2.png}
		\caption{椭圆曲线$y^2=x^3-2x+1$\label{fig:EC-2}}
	\end{figure}
\end{example}



\begin{example}
	椭圆曲线：$y^2=x^3-2x+2$\par
	\begin{SageMath}{椭圆曲线} 
		\begin{verbatim}
		# y^2=x^3-2x+2
		p= plot(EllipticCurve([0,0,0,-2,2]),gridlines='true', xmin=-4, xmax=4, 
		   ymin=-3, ymax=3,legend_label='$y^2=x^3-2x+2$')
		show(p)
		\end{verbatim}
	\end{SageMath}
	\begin{figure}[!htbp]
		\centering
		\includegraphics[width=0.6\textwidth]{figure/EC-3.png}
		\caption{椭圆曲线$y^2=x^3-2x+2$\label{fig:EC-3}}
	\end{figure}
\end{example}

通过定义恰当的“加法”运算，椭圆曲线上的点全体构成一个加法群， 正因为椭圆曲线存在加法结构，所以它包含了很多重要的数论信息。下面我们看看椭圆曲线上的加法群的构建。\par

\begin{itemize}
	\item 单位元：$O$为单位元，椭圆曲线上的所有点$P$有$P+O=P$，$O$也是一个椭圆曲线上的一个点，是一个无穷远的点。
	\item 逆元：对点$P=(x,y)$，其加法逆元为$(x,-y)$，记为$-P$，$P+(-P)=O$，由此也可以定义减法$P-P=O$
	\item 加法：对于两个不同且不互逆的点$P,Q$,我们画一条通过$P,Q$的直线，与椭圆曲线交于一点，这个交点是唯一的(除非所做的直线是$P$或$Q$的切线)，此交点的逆元为$R$，定义$P+Q=R$。加法定义如图\ref{fig:ECC-add}所示。
	\item 倍数：点$P$的倍数定义为，在$P$点做椭圆曲线的一条切线，设切线与椭圆曲线交于一点，$R$为此交点的逆元，定义$2P=P+P=R$，一般将$\overbrace{Q+Q+\ldots+Q}^{n\text{个}Q}$记为$nQ$。
\end{itemize}
可以证明以上定义的加法运算具有交换律和结合律等一般性质。\par

\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.6\textwidth]{figure/ECC-add.jpg}
	\caption{椭圆曲线加法定义图示\label{fig:ECC-add}}
\end{figure}

\section{有限域上的椭圆曲线}
为了简单起见，我们通常考虑在有限域$GF(p)$上的椭圆曲线，$p$为大于3的素数，在有限域$GF(p)$上的曲线$y^2=x^3+ax+b  \left( a,b\in GF(p),4a^3+27b^2\neq 0 \right) $称为有限域上的椭圆曲线，通常记为$E_p(a,b)$。\par

椭圆曲线的定义也要求曲线是非奇异的(即处处可导的)。几何上来说，这意味着图像里面没有尖点、自相交或孤立点。代数上来说，这成立当且仅当判别式$\delta =4a^3+27b^2$不等于0，这里主要是满足其可导性。
\par

我们看看同一方程在不同域上的曲线。\par

\begin{example}
	椭圆曲线：$y^2=x^3-2x$在有限域$GF(11)$和实数域上表示的曲线。\par
	\begin{SageMath}{椭圆曲线} 
		\begin{verbatim}
		# y^2=x^3-2x在有限域GF(11)
		p=plot(EllipticCurve(GF(11),[0,0,0,-2,0]),gridlines='true', 
		xmin=-11, xmax=11, ymin=-30, ymax=30,
		legend_label='$y^2=x^3-2x,GF(11)$')
		# y^2=x^3-2x在实数域 
		p+=plot(EllipticCurve([0,0,0,-2,0]),gridlines='true', color=hue(1), 
		xmin=-11, xmax=11,ymin=-30, ymax=30,legend_label='$y^2=x^3-2x$')
		show(p)
		\end{verbatim}
	\end{SageMath}
	\begin{figure}[!htbp]
		\centering
		\includegraphics[width=0.6\textwidth]{figure/EC-R-GF.png}
		\caption{椭圆曲线$y^2=x^3-2x$在有限域$GF(11)$和实数域上的图\label{fig:EC-R-GF}}
	\end{figure}
\end{example}
有限域椭圆曲线构成的群如下：
\begin{itemize}
	\item 单位元：$O$为单位元，椭圆曲线上的所有点$P$有$P+O=P$，$O$也是一个椭圆曲线上的一个点，是一个无穷远的点。
	\item 逆元：对点$P=(x,y)$，其加法逆元为$(x,-y)$，记为$-P$，$P+(-P)=O$，由此也可以定义减法$P-P=O$
	\item 加法：对于两个不同且不互逆的点$P(x_1,y_1),Q(x_2,y_2),x_1 \neq x_2$,$P(x_1,y_1)+Q(x_2,y_2)=S(x_3,y_3)$,其中：\\
	$x_3=\lambda ^2-x_1-x_2 \pmod{p}$\\
	$y_3=\lambda (x_1-x_3)-y_1 \pmod{p}$\\
	$\lambda=\dfrac{y_2-y_1}{x_2-x_1}$
	
	\item 倍数：点$P$的倍数定义为，$2P=P(x_1,y_1)+P(x_1,y_1)=S(x_3,y_3)$，其中：\\
	$x_3=\lambda ^2-2x_1 pmod{p}$\\
	$y_3=\lambda (x_1-x_3)-y_1 \pmod{p}$\\
	$\lambda=\dfrac{3x_1^2+a}{2y_1}$,其中$a$是方程中的常数。
\end{itemize}
\par

\textit{假设$E/F_p$是一个椭圆曲线，$e\geq 1$,如果$(x_1,y_1),x_1,y_1 \in F_{p^e}$，满足曲线方程$E$，我们说点$(x_1,y_1)$在椭圆曲线上。当$e=1$时，点$(x_1,y_1)$定义在基础域(base field)$F_p$上，当$e> 1$时，点$(x_1,y_1)$定义在域$F_p$的扩展上。在域$F_{p^e}$上曲线$E$上的所有点，包括无穷远点(the point of infinity)$O$，我们记为$E(F_{p^e})$,用$|E(F_{p^e})|$表示椭圆曲线上点的个数。}\par

\textit{根据哈赛(Hase)的研究结果，我们有$|E(F_{p^e})|=p^e+1-t$，其中$|t| \leq 2\sqrt{p^e}$，这表明$|E(F_{p^e})|$非常接近$p^e-1$。对于$E(F_{p})$来说，这个值为$p+1$.}\cite{Boneh-AppliedCry}
\par

\vspace{0.5cm}
\begin{example}\cite{李浪-密码工程}
	$GF(11)$上的一个椭圆曲线$E_{11}(1,6):y^2 = x^3+x+6 \pmod{11}$构成的交换群。	
\end{example}
\begin{solution}
	1、计算椭圆曲线上所有的点
	\par
	对于$GF(11)$上的每一个点$x$计算$s=x^3+x+6 \pmod{11}$，然后求解$y^2=s \pmod{11}$，如果此方程有解(即s为模11的平方剩余)，解为$y$，则$(x,\pm y)$是$E_{11}(1,6)$上的点，按照这个方法，我们可以获得$E_{11}(1,6)$上的点，共12个点：\\
	$(2,4),(2,7),(3,5),(3,6),(5,2),(5,9),(7,2),(7,9),(8,3),(8,8),(10,2),(10,9)$
	\par
	2、交换群
	\par
	我们可以看到$(2,4)$和$(2,7)$互为逆元,下面我们计算$(2,4)+(3,5)$:\\
	$\lambda = \dfrac{y_2-y_1}{x_2-x_1} = \dfrac{5-4}{3-2} =1 $\\
	$x_3=\lambda ^2-x_1-x_2 \pmod{11}=1^2 - 2-3 \pmod{11}=7$\\
	$y_3=\lambda (x_1-x_3)-y_1 \pmod{11}=(2-7)-4=2$\\
	$(2,4)+(3,5)=(7,2)$,可以看到$(7,2)$仍然是椭圆曲线上的点，可见加法运算在$E_{11}(1,6)$上是封闭的。
\end{solution}
\par

\begin{example}\cite{杨波-现代密码学}
	在$E_{23}(1,1)$上计算$P+Q,P=(3,10),Q=(9,7)$。
\end{example}
\begin{solution}
	$\lambda = \dfrac{y_2-y_1}{x_2-x_1} = \dfrac{7-10}{9-3} =\dfrac{-3}{6} =\dfrac{-1}{2}=11 \pmod{23}$ \footnote{此处计算解释，我们需要找到一个数$a,2a=1\pmod{23}$，可知$a=12,-12 \pmod{23}=11$ }\par
	$x_3=\lambda ^2-x_1-x_2 \pmod{23}=11^2 - 3-9 \pmod{23}=17$\\
	$y_3=\lambda (x_1-x_3)-y_1 \pmod{23}=11(3-17)-10=-164=20$\\
	$P+Q=(17,20)$,结果仍然为$E_{23}(1,1)$中的点。
\end{solution}
\par

\section{构造密码算法}
要想利用椭圆曲线构造密码算法，从大的方面来说，要解决以下几个问题：
\par
\begin{enumerate}
	\item 将一个信息，也就是一个二进制串或者一个数，映射到椭圆曲线的一个点，同时也可将椭圆曲线上的一个点映射到一个信息。
	\item 然后在椭圆曲线上找到一个计算困难问题，但这个困难问题当有某个信息时要变得不困难。
	\item 设计一个信息变换或计算过程。
\end{enumerate}
\par
下面我们依次看看以上这几个问题的考虑。

\subsection{消息到椭圆曲线上的映射}
设消息是$m,0\leq m \leq M $,$E:y^3=x^2+ax+b$，给定一个整数k，实际中k在30~50之间取值，在这里我们取k=30，对明文m计算一系列x，$x=\{mk+j,j=0,1,2,\ldots\}=\{30m+j,j=0,1,2,\ldots\}$,直到$x^2+ax+b \pmod{p}$是平方根，那么就将m映射到椭圆曲线上这一点$(x,\sqrt{x^2+ax+b})$。\par

反之，有一个椭圆曲线上的一点$(x,y)$，我们将其还原为消息m的过程为$m=\lfloor \dfrac{x}{30}\rfloor$.

\subsection{椭圆曲线上的计算困难问题}
在$E_p(a,b)$上考虑方程$Q=kP$，$Q,P\in E_p(a,b),k< p$,我们知道了$k,P$很容易求解$Q$，但是知道了$P,Q$，求确$k$是一个困难问题，这就是椭圆曲线上的离散对数问题。

\subsection{椭圆曲线上的密码算法}

\subsubsection{ECC(Elliptic Curve Cryptography)加密算法}
通常软件实现采用的域为$GF(p)$域，在硬件实现的采用$GF(2^m)$域，下面我们看一个经典的$GF(p)$域上的ECC算法。\cite{高胜-blockchain}\par
ECC属于公钥密码体制，下面假设用Alice给Bob准备发送一个秘密信息的实例来说明整个过程。\par

\vspace{0.5cm}
\textbf{(1)Bob生成公私钥对}\par
\begin{itemize}
	\item 选择椭圆曲线$E:y^2=x^3+ax+b \pmod{p}$，构造群$E_p(a,b)$.
	\item 在$E_p(a,b)$上挑选生成元$g=(x_0,y_0)$,$g$应使得满足$ng=O$的最小n是一个非常大的素数。
	\item 选择一个随机数$\alpha,\alpha \in [1,n-1]$,计算$\beta=\alpha g$。
	\item Bob的公钥为$(E_p(a,b),n,g\beta)$，私钥为$\alpha$。
\end{itemize}

\textbf{(2)Alice对消息m加密}\par
\begin{itemize}
	\item 选择一个随机数$k,k\in [1,n-1]$.
	\item 计算点$C_1=(x_1,y_1)=kg$.
	\item 随机选择一个点$P_t=(x_t,y_t)$，计算$C_2=P_t+k\beta$.
	\item 计算密文$C_3=mx_t+y_t$.
	\item 将$(C_1,C_2,C_3)$做为密文发给Bob。
\end{itemize}

\textbf{(3)Bob对密文$(C_1,C_2,C_3)$解密}\par
\begin{itemize}
	\item 使用私钥$\alpha$计算$C_2-\alpha C_1=(x'_t,y'_t)=P'_t$.
	\item 计算$m= \dfrac{(C_3-y'_t)}{x'_t}$，$m$即为解密后的明文。
\end{itemize}
\par
\vspace{0.5cm}

我们简单看看以上过程的正确性：\par
$\alpha C_1=\alpha kg=k \alpha g=k\beta $\par
$(x'_t,y'_t)=C_2 \alpha C_1=P_t +k\beta -k\beta=P_t=(x_t,y_t)$\par
$\dfrac{C_3-y'_t}{x'_t}=\dfrac{mx_t+y_t-y'_t}{x'_t}=m$\par

\subsubsection{Diffie-Hellman密钥交换}
下面我们介绍一下如何用椭圆曲线进行DH密钥交换.\par
\begin{itemize}
	\item 选一个素数$p\approx 2^{180}$和两个参数$a,b$，构造$E_p(a,b)$。
	\item 取$E_p(a,b)$的一个生成元$G_1(x_1,y_1)$，使G的阶n是一个非常大的素数。\footnote{G的阶是满足$nG=O$的最小正整数n。}
	\item $E_p(a,b),G,n$公开。
	\item 用户A任选$n_A,n_A \in [1,n-1]$，$n_A$为A的私钥，$P_A=n_A G$是A的公钥。
	\item 用户B任选$n_B,n_B \in [1,n-1]$，$n_B$为B的私钥，$P_B=n_B G$是B的公钥。
	\item A、B双方利用对方的公钥和自身的私钥，即可产生双方共享的密钥$K$,A计算$K=n_AP_B$,B计算$K=n_BP_A$
\end{itemize}

